// 类似的题：907.子数组的最小值之和
// 统计每个元素作为最小元素时的贡献，用单调栈找到每个元素左、右的下一个更大元素

class Solution
{
public:
    int totalStrength(vector<int> &strength)
    {
        int n = strength.size();
        vector<long long> strengthPrefixSum(n + 1, 0);
        partial_sum(strength.begin(), strength.end(), strengthPrefixSum.begin() + 1, PlusAndModLL());
        vector<long long> strengthDoublePrefixSum(n + 2, 0);
        partial_sum(strengthPrefixSum.begin(), strengthPrefixSum.end(), strengthDoublePrefixSum.begin() + 1, PlusAndModLL());

        vector<int> firstGreaterAhead(n);
        vector<int> firstNoLessAfter(n);
        stack<int> s;
        for (int i = 0; i < n; ++i)
        {
            while (!s.empty())
            {
                if (strength[s.top()] >= strength[i])
                {
                    s.pop();
                }
                else
                {
                    break;
                }
            }
            if (s.empty())
            {
                firstGreaterAhead[i] = -1;
            }
            else
            {
                firstGreaterAhead[i] = s.top();
            }
            s.push(i);
        }

        s = stack<int>();
        for (int i = n - 1; i >= 0; --i)
        {
            while (!s.empty())
            {
                if (strength[s.top()] > strength[i])
                {
                    s.pop();
                }
                else
                {
                    break;
                }
            }
            if (s.empty())
            {
                firstNoLessAfter[i] = n;
            }
            else
            {
                firstNoLessAfter[i] = s.top();
            }
            s.push(i);
        }

        long long result = 0LL;
        for (int i = 0; i < n; ++i)
        {
            int left = firstGreaterAhead[i] + 1;
            int right = firstNoLessAfter[i] - 1;
            int weekestStrength = strength[i];
            long long sumStrength = weekestStrength * ((((i - left + 1) * (strengthDoublePrefixSum[right + 2] - strengthDoublePrefixSum[i + 1])) % 1000000007LL - ((right - i + 1) * (strengthDoublePrefixSum[i + 1] - strengthDoublePrefixSum[left])) % 1000000007LL)) % 1000000007LL;
            result += sumStrength;
            result %= 1000000007LL;
        }
        result = (result + 1000000007LL) % 1000000007LL;
        return static_cast<int>(result);
    }

    class PlusAndModLL
    {
    public:
        constexpr long long operator()(const long long &lhs, const long long &rhs) const
        {
            return (lhs + rhs) % 1000000007LL;
        }
    };
};